Article 4121

Title of the article

Construction of an optimal spanning tree as a tool to ensure the stability of the communication network 

Authors

Boris F. Mel'nikov, Doctor of physical and mathematical sciences, professor of the faculty of computational mathematics and cybernetics, Shenzhen MSU–BIT University (1 International University Park Road, Dayun New Town, Longgang District, Shenzhen, Guangdong Province, PRC, 517182, China), E-mail: bormel@mail.ru
Yuliya Yu. Terent'eva, Candidate of engineering sciences, head of the department of analysis and methodology for improving information telecommunication systems, Center for Information Technologies and Systems of State Authorities (building 1, 19 Presnensky Val street, Moscow, Russia), E-mail: terjul@mail.ru 

Index UDK

004.023+519.173.1. 

DOI

10.21685/2072-3059-2021-1-4 

Abstract

Background. When designing/modernizing and operating communication networks, one of the most important tasks is to ensure its stability. Real communication networks, as a rule, are large-scale, and, accordingly, it is important to obtain solutions as close to optimal as possible as a necessary factor in saving resources. The stability of the communication network in terms of survivability is directly related to the number of independent routes between the vertices of the modeling graph that form the information communication directions. The authors will consider the issue of developing algorithms for constructing independent paths and show the effectiveness of using the procedures for forming an optimal spanning tree to solve the problem of ensuring the stability of the communication network. Purpose of the study. Development of algorithms for constructing optimal independent paths between given vertices of the graph in order to ensure the required livability of the communication network while minimizing the cost of upgrading the communication network topology.
Materials and methods. Algorithms of graph theory, both well-known and newly developed, are used. In particular, greedy algorithms are considered, as well as other heuristic algorithms.
Results. Heuristic algorithms for constructing optimal independent paths between the given vertices of the communication network graph are developed, the effectiveness of using the approach of forming an optimal spanning tree for solving the problem of ensuring the stability of the communication network is shown.
Conclusions. Improvement of algorithms for constructing an optimal spanning tree was proposed, which was used to construct independent paths between the vertices of a graph, and the efficiency of using procedures for forming a spanning tree to solve the problem of ensuring the stability of a communication network was shown. 

Key words

communication network stability, communication network graph, heuristic algorithms For citation 

Download PDF
References

1. Melnikov B.F., Meshchanin V.Y., Terentyeva Y.Y. Implementation of optimality criteria in the design of communication networks. Journal of Physics: Conference Series, International Scientific Conference ICMSIT–2020: Metrological Support of Innovative Technological, ICMSIT-2020 (paper 3095). Available at: http://conf.domnit.ru/en/conferences/icmsit-2020-en/
2. Bulynin A.G., Mel'nikov B.F., Meshchanin V.Yu., Terent'eva Yu.Yu. Optimization problems arising in the design of high-dimensional communication networks, and some heuristic methods for their solution. Informatizatsiya i svyaz' = Informatization and communication. 2020;1:34–40. (In Russ.). Available at: https://elibrary.ru/item.asp?id=42839357
3. Bulynin A.G., Mel'nikov B.F., Meshchanin V.Yu., Terent'eva Yu.Yu. Algorithms for designing communication networks using greedy heuristics of different types. Informatsionnye tekhnologii i nanotekhnologii (ITNT-2020): sb. tr. po materialam VI Mezhdunar. konf. i molodezhnoy shkoly = Information technology and nanotechnology (ITNT-2020): proceedings of the 6th International conference and youth school. Samara, 2020:856–860. (In Russ.). Available at: https://www.elibrary.ru/item.asp?id=43576630
4. Kruskal J. On the shortest spanning subtree of a graph and the traveling salesman problem. Proceedings of the American Mathematical Society. 1956;7(1):48–50. doi:10.1090/S0002-9939-1956-0078686-7
5. Kormen T., Leyzerson Ch., Rivest R., Shtayn K. Algoritmy. Postroenie i analiz = Algorithms. Construction and analysis. Moscow: Vil'yams, 2005:1296. (In Russ.)
6. Goodrich M., Tamassia R. Data Structures and Algorithms in Java, Fourth Edition. N.J.: John Wiley & Sons, 2006.
7. Prim R. Shortest connection networks and some generalizations. Bell System Technical Journal. 1957;36(6):1389–1401. doi:10.1002/j.1538-7305.1957.tb01515
8. Mel'nikov B.F., Terent'eva Yu.Yu. Construction of communication networks: on the application of Kruskal algorithm in problems of large dimensions. International Journal of Open Information Technologies. 2021;9(1):13–21. (In Russ.)
9. Ore O. Teoriya grafov = Graph theory. Moscow: Mir, 1980. (In Russ.)

 

Дата создания: 14.05.2021 10:28
Дата обновления: 14.05.2021 10:53